package zisu.algorithm.algorithm.Queue;



import java.util.Arrays;

/**
 * @Author: 蔡翔
 * @Date: 2019/12/3 14:35
 * @Version 1.0
 */
public class LoopQueue<E> implements Queue<E> {
    private E[] data;
    private int front,tail;
    private int size;

    public LoopQueue(int capacity){
        front = 0;
        tail = 0;
        size = 0;
        data = (E[]) new Object[capacity+1];
    }
    public LoopQueue(){
        this(10);
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return front == tail;
    }

    @Override
    public void enQueue(E e) {
        if((tail+1)%data.length == front){
            resize(getCapacity()*2);
        }
        data[tail] = e;
        tail = (tail+1)%data.length;
        size++;
    }

    private void resize(int newCapacity) {
        E[] newData = (E[])new Object[newCapacity+1];
        for(int i=0;i<size;i++){
            newData[i] = data[(front+i)%data.length];
        }
        data = newData;
        front = 0;
        tail = size;
    }

    @Override
    public E deQueue() {
        if(isEmpty()){
            throw new RuntimeException("Can not dequeue from an empty");
        }
        E ret = data[front];
        data[front] = null;
        front = (front+1)%data.length;
        size--;

        if(size == getCapacity()/4  && getCapacity()/2!=0){
            resize(getCapacity()/2);
        }
        return ret;
    }

    @Override
    public E getFront() throws Exception {
        if(isEmpty()){
            throw new Exception("队列不能为空");
        }
        return data[front];
    }

    @Override
    public Integer getCapacity() {
        return data.length-1;
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append(String.format("LoopQueue: size = %d , capacity= %d\n",size,getCapacity()));
        stringBuilder.append("Front [");
        for (int i = front ; i != tail ; i = (i + 1) % data.length){
            stringBuilder.append(data[i]);
            if(i!= (size-1)){
                stringBuilder.append(",");
            }
        }
        stringBuilder.append("] tail");
        return stringBuilder.toString();
    }

    public static void main(String[] args) {
        LoopQueue<Integer> loopQueue = new LoopQueue<>();
        for(int i =0 ; i < 10; i++){
            loopQueue.enQueue(i);
            System.out.println(loopQueue.toString());

            if(i%3 ==2){
                final Integer integer =  loopQueue.deQueue();
                System.out.println(loopQueue.toString());
            }
        }
        //System.out.println(loopQueue);
    }
}
